package linkedin;

import treesNgraphs.TreeNode;

import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * Created by Tzachi on 26/10/2014.
 *
 * Print a tree in Level Order with a newline after each depth
 *
 * Sample input:
 *
 *          1
 *         / \
 *        3   5
 *       / \   \
 *      2   4   7
 *     /     \
 *    9       8
 *
 * Expected output:
 *    1
 *    3 5
 *    2 4 7
 *    9 8
 *    ==========
 */
public class PrintTreeByLevel {

    public static void printTree(TreeNode<Integer> root){
        Queue<TreeNode<Integer>> nodes = new LinkedBlockingQueue<>();
        Queue<TreeNode<Integer>> tmpQueue = new LinkedBlockingQueue<>();
        nodes.add(root);
        while (!nodes.isEmpty()){
            TreeNode<Integer> node = nodes.poll();
            System.out.print(node.getValue() + " ");
            if (node.hasLeftChild()){
                tmpQueue.add(node.getLeftChild());
            }
            if (node.hasRightChild()){
                tmpQueue.add(node.getRightChild());
            }
            if  (nodes.isEmpty()){
                nodes.addAll(tmpQueue);
                tmpQueue.clear();
                System.out.println();
            }
        }
    }

    public static void main(String[] args) {
        TreeNode<Integer> root = new TreeNode<>(1);
        TreeNode<Integer> leftChild = new TreeNode<>(3);
        leftChild.setLeftChild(new TreeNode<>(2));
        leftChild.setRightChild(new TreeNode<>(4));
        root.setLeftChild(leftChild);
        TreeNode<Integer> rightChild = new TreeNode<>(5);
        rightChild.setRightChild(new TreeNode<>(7));
        root.setRightChild(rightChild);
        printTree(root);
    }
}
